#include <vector>
//#include <algorithm>
#include <iostream>
using namespace std;

template <typename Comparable>
void myswap(Comparable &a, Comparable &b)
{
	Comparable c;
	c = a;
	a = b;
	b = c;
}

/*
 *Insertion sort. O(N^2)
 */
template <typename Comparable>
void insertionSort(vector<Comparable> &a)
{
	int j;

	for (int p = 1; p < a.size(); p++) {
		Comparable tmp = a[p];	
		for (j = p; j > 0 && tmp < a[j-1]; j--)
			a[j] = a[j-1];
		a[j] = tmp;
	}
}

/*
 *Shell sort. 
 */
template <typename Comparable>
void shellsort(vector<Comparable> a)
{
	int j; 
	
	for (int gap = a.size()/2; gap > 0; gap /= 2) {
		for (int i = gap; i < a.size(); i++) {
			Comparable tmp =a[i];
			for (j = i; j >= gap && tmp < a[j-gap]; j -= gap)	
				a[j] = a[j-gap];
			a[j] = tmp;
		}	
	}
}

/*
 *merge sort.
 */
template <typename Comparable>
void mergeSort(vector<Comparable> &a, vector<Comparable> &tmpArray, 
			   int left, int right);

template <typename Comparable>
void mergeSort(vector<Comparable> &a)
{
	vector<Comparable> tmpArray(a.size());

	mergeSort(a, tmpArray, 0, a.size() - 1);
}

template <typename Comparable>
void merge(vector<Comparable> &a, vector<Comparable> &tmpArray, 
		   int leftpos, int rightpos, int rightend);

template <typename Comparable>
void mergeSort(vector<Comparable> &a, vector<Comparable> &tmpArray, int left, int right)
{
	if (left < right) {
		int center = (left + right) / 2;	
		mergeSort(a, tmpArray, left, center);
		mergeSort(a, tmpArray, center+1, right);
		merge(a, tmpArray, left, center+1, right);
	}
}
template <typename Comparable>
void merge(vector<Comparable> &a, vector<Comparable> &tmpArray, 
		   int leftpos, int rightpos, int rightend)
{
	int leftend = rightpos - 1;
	int tmppos = leftpos;
	int numElements = rightend - leftpos + 1;

	while (leftpos <= leftend && rightpos<=rightend) {
		if (a[leftpos] <= a[rightpos])	
			tmpArray[tmppos++] = a[leftpos++];
		else
			tmpArray[tmppos++] = a[rightpos++];
	}

	while (leftpos <= leftend)
		tmpArray[tmppos++] = a[leftpos++];
	while (rightpos <= rightend)
		tmpArray[tmppos++] = a[rightpos++];

	for (int i = 0; i < numElements; i++, rightend--)
		a[rightend] = tmpArray[rightend];
}

/*
 *quick sort
 */

template <typename Comparable>
void quicksort(vector<Comparable> &a, int left, int right);

template <typename Comparable>
void quicksort(vector<Comparable> &a)
{
	quicksort(a, 0, a.size() - 1);
}

template <typename Comparable>
void quicksort(vector<Comparable> &a, int left, int right)
{
	if (left + 10 <= right) {
		Comparable pivot = median3(a, left, right);		

		int i = left, j = right - 1;
		for ( ; ;) {
			while (a[++i] < pivot) {}
			while (pivot < a[--j]) {}
			if (i < j)
				myswap(a[i], a[j]);
			else 
				break;
		}

		myswap(a[i], a[right - 1]);

		quicksort(a, left, i - 1);
		quicksort(a, i + 1, right);
	} 
	else 
		insertionSort(a);
}

template <typename Comparable>
const Comparable & median3(vector<Comparable> &a, int left, int right)
{
	int center = (left + right) /2;
	if (a[center] < a[left])
		myswap(a[left], a[center]);
	if (a[right] < a[left])
		myswap(a[right], a[left]);
	if (a[right] < a[center])
		myswap(a[center], a[right]);

	myswap(a[center], a[right-1]);
	return a[right-1];
}

/*
 *test program.
 */
int main()
{
	vector<int> array;
	
	for (int i = 10; i > 0; i--) 
		array.push_back(i);	
	cout << "before sort:" << endl;
	for (int i = 0; i < array.size(); i++)
		cout << array[i] << '\t';
	cout << endl;

	//insertionSort(array);
	//shellsort(array);
	//quicksort(array);
	mergeSort(array);

	cout << "after sort:" << endl;
	for (int i = 0; i < array.size(); i++)
		cout << array[i] << '\t';
	cout << endl;
	return 0;
}
